package com.itzmn.newcode.offer;

import java.util.ArrayList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/17 14:18
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  剑指Offer  得到树的深度
 *
 *  思路：
 *   遍历树
 *               1
 *            2     3
 *         4    5  6   78
 *      9
 */
public class GetTreeHight {

    public static void main(String[] args) {

        new GetTreeHight().init();

    }

    private void init() {

        TreeNode tree = createTree(new int[]{1, 2, 3, 4, 5, 6, 78, 9});

        TreeDepth(tree);
    }

    /**
     * 创建二叉树
     * @param arrs
     * @return
     */
    public TreeNode createTree(int[] arrs){

        ArrayList<TreeNode> treeNodes = new ArrayList<>();
        for (int i:arrs){
            treeNodes.add(new TreeNode(i));
        }
        TreeNode root = treeNodes.get(0);

        for (int i = 0; i < arrs.length/2; i++) {
            if (i*2+1<arrs.length){
                treeNodes.get(i).left=treeNodes.get(i*2+1);
            }
            if(i*2+2<treeNodes.size()){//避免偶数的时候 下标越界
                treeNodes.get(i).right=treeNodes.get(i*2+2);
            }
        }

        return root;

    }

    public int TreeDepth(TreeNode root) {

        Integer getdata = getdata(root, 0);
        System.out.println(getdata);
        return getdata;
    }

    /**
     *
     *  *               1
     *  *            2     3
     *  *         4    5  6   78
     *  *      9
     * @param node
     * @param count
     * @return
     */
    public Integer getdata(TreeNode node,int count){
        if (node == null){
            return 0;
        }

        count++;
        if (node.left==null && node.right==null){

            return count;
        }

        int leftval = count;
        if (node.left !=null){
            leftval  = getdata(node.left, count);
        }
        int rval = count;
        int rightval = count;
        if (node.right !=null){
            rightval = getdata(node.right,rval);
        }
        return Math.max(leftval,rightval);
    }
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }


}
